use crate::src::struct_and_type::{
    RBTree, RBTreeCompareFunc, RBTreeKey, RBTreeNode, RBTreeNodeColor, RBTreeNodeSide, RBTreeValue,
};
use :: libc;
extern "C" {
    fn malloc(_: u64) -> *mut libc::c_void;
    fn free(_: *mut libc::c_void);
}
pub const RB_TREE_NODE_BLACK: RBTreeNodeColor = 1;
pub const RB_TREE_NODE_RED: RBTreeNodeColor = 0;
pub const RB_TREE_NODE_RIGHT: RBTreeNodeSide = 1;
pub const RB_TREE_NODE_LEFT: RBTreeNodeSide = 0;
extern "C" fn rb_tree_node_side(mut node: *mut RBTreeNode) -> RBTreeNodeSide {
    if (unsafe { (*(*node).parent).children[RB_TREE_NODE_LEFT as i32 as usize] }) == node {
        return RB_TREE_NODE_LEFT;
    } else {
        return RB_TREE_NODE_RIGHT;
    };
}
extern "C" fn rb_tree_node_sibling(mut node: *mut RBTreeNode) -> *mut RBTreeNode {
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;
    side = rb_tree_node_side(node);
    return unsafe {
        (*(*node).parent).children[(1 as i32 as u32).wrapping_sub(side as u32) as usize]
    };
}
#[no_mangle]
pub extern "C" fn rb_tree_node_uncle(mut node: *mut RBTreeNode) -> *mut RBTreeNode {
    return rb_tree_node_sibling(unsafe { (*node).parent });
}
extern "C" fn rb_tree_node_replace(
    mut tree: *mut RBTree,
    mut node1: *mut RBTreeNode,
    mut node2: *mut RBTreeNode,
) {
    let mut side: i32 = 0;
    if !node2.is_null() {
        (unsafe { (*node2).parent = (*node1).parent });
    }
    if (unsafe { (*node1).parent }).is_null() {
        (unsafe { (*tree).root_node = node2 });
    } else {
        side = rb_tree_node_side(node1) as i32;
        (unsafe { (*(*node1).parent).children[side as usize] = node2 });
    };
}
extern "C" fn rb_tree_rotate(
    mut tree: *mut RBTree,
    mut node: *mut RBTreeNode,
    mut direction: RBTreeNodeSide,
) -> *mut RBTreeNode {
    let mut new_root: *mut RBTreeNode = 0 as *mut RBTreeNode;
    new_root =
        unsafe { (*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize] };
    rb_tree_node_replace(tree, node, new_root);
    (unsafe {
        (*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize] =
            (*new_root).children[direction as usize]
    });
    (unsafe { (*new_root).children[direction as usize] = node });
    (unsafe { (*node).parent = new_root });
    if !(unsafe { (*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize] })
        .is_null()
    {
        (unsafe {
            (*(*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize]).parent =
                node
        });
    }
    return new_root;
}
#[no_mangle]
pub extern "C" fn rb_tree_new(mut compare_func: RBTreeCompareFunc) -> *mut RBTree {
    let mut new_tree: *mut RBTree = 0 as *mut RBTree;
    new_tree = (unsafe { malloc(::core::mem::size_of::<RBTree>() as u64) }) as *mut RBTree;
    if new_tree.is_null() {
        return 0 as *mut RBTree;
    }
    (unsafe { (*new_tree).root_node = 0 as *mut RBTreeNode });
    (unsafe { (*new_tree).num_nodes = 0 as i32 });
    (unsafe { (*new_tree).compare_func = compare_func });
    return new_tree;
}
extern "C" fn rb_tree_free_subtree(mut node: *mut RBTreeNode) {
    if !node.is_null() {
        rb_tree_free_subtree(unsafe { (*node).children[RB_TREE_NODE_LEFT as i32 as usize] });
        rb_tree_free_subtree(unsafe { (*node).children[RB_TREE_NODE_RIGHT as i32 as usize] });
        (unsafe { free(node as *mut libc::c_void) });
    }
}
#[no_mangle]
pub extern "C" fn rb_tree_free(mut tree: *mut RBTree) {
    rb_tree_free_subtree(unsafe { (*tree).root_node });
    (unsafe { free(tree as *mut libc::c_void) });
}
extern "C" fn rb_tree_insert_case1(mut tree: *mut RBTree, mut node: *mut RBTreeNode) {
    if (unsafe { (*node).parent }).is_null() {
        (unsafe { (*node).color = RB_TREE_NODE_BLACK });
    } else {
        rb_tree_insert_case2(tree, node);
    };
}
extern "C" fn rb_tree_insert_case2(mut tree: *mut RBTree, mut node: *mut RBTreeNode) {
    if (unsafe { (*(*node).parent).color }) as u32 != RB_TREE_NODE_BLACK as i32 as u32 {
        rb_tree_insert_case3(tree, node);
    }
}
extern "C" fn rb_tree_insert_case3(mut tree: *mut RBTree, mut node: *mut RBTreeNode) {
    let mut grandparent: *mut RBTreeNode = 0 as *mut RBTreeNode;
    let mut uncle: *mut RBTreeNode = 0 as *mut RBTreeNode;
    grandparent = unsafe { (*(*node).parent).parent };
    uncle = rb_tree_node_uncle(node);
    if !uncle.is_null() && (unsafe { (*uncle).color }) as u32 == RB_TREE_NODE_RED as i32 as u32 {
        (unsafe { (*(*node).parent).color = RB_TREE_NODE_BLACK });
        (unsafe { (*uncle).color = RB_TREE_NODE_BLACK });
        (unsafe { (*grandparent).color = RB_TREE_NODE_RED });
        rb_tree_insert_case1(tree, grandparent);
    } else {
        rb_tree_insert_case4(tree, node);
    };
}
extern "C" fn rb_tree_insert_case4(mut tree: *mut RBTree, mut node: *mut RBTreeNode) {
    let mut next_node: *mut RBTreeNode = 0 as *mut RBTreeNode;
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;
    side = rb_tree_node_side(node);
    if side as u32 != rb_tree_node_side(unsafe { (*node).parent }) as u32 {
        next_node = unsafe { (*node).parent };
        rb_tree_rotate(
            tree,
            unsafe { (*node).parent },
            (1 as i32 as u32).wrapping_sub(side as u32) as RBTreeNodeSide,
        );
    } else {
        next_node = node;
    }
    rb_tree_insert_case5(tree, next_node);
}
extern "C" fn rb_tree_insert_case5(mut tree: *mut RBTree, mut node: *mut RBTreeNode) {
    let mut parent: *mut RBTreeNode = 0 as *mut RBTreeNode;
    let mut grandparent: *mut RBTreeNode = 0 as *mut RBTreeNode;
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;
    parent = unsafe { (*node).parent };
    grandparent = unsafe { (*parent).parent };
    side = rb_tree_node_side(node);
    rb_tree_rotate(
        tree,
        grandparent,
        (1 as i32 as u32).wrapping_sub(side as u32) as RBTreeNodeSide,
    );
    (unsafe { (*parent).color = RB_TREE_NODE_BLACK });
    (unsafe { (*grandparent).color = RB_TREE_NODE_RED });
}
#[no_mangle]
pub extern "C" fn rb_tree_insert(
    mut tree: *mut RBTree,
    mut key: RBTreeKey,
    mut value: RBTreeValue,
) -> *mut RBTreeNode {
    let mut node: *mut RBTreeNode = 0 as *mut RBTreeNode;
    let mut rover: *mut *mut RBTreeNode = 0 as *mut *mut RBTreeNode;
    let mut parent: *mut RBTreeNode = 0 as *mut RBTreeNode;
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;
    node = (unsafe { malloc(::core::mem::size_of::<RBTreeNode>() as u64) }) as *mut RBTreeNode;
    if node.is_null() {
        return 0 as *mut RBTreeNode;
    }
    (unsafe { (*node).key = key });
    (unsafe { (*node).value = value });
    (unsafe { (*node).color = RB_TREE_NODE_RED });
    (unsafe { (*node).children[RB_TREE_NODE_LEFT as i32 as usize] = 0 as *mut RBTreeNode });
    (unsafe { (*node).children[RB_TREE_NODE_RIGHT as i32 as usize] = 0 as *mut RBTreeNode });
    parent = 0 as *mut RBTreeNode;
    rover = unsafe { &mut (*tree).root_node };
    while !(unsafe { *rover }).is_null() {
        parent = unsafe { *rover };
        if (unsafe {
            ((*tree).compare_func).expect("non-null function pointer")(value, (**rover).value)
        }) < 0 as i32
        {
            side = RB_TREE_NODE_LEFT;
        } else {
            side = RB_TREE_NODE_RIGHT;
        }
        rover = (unsafe { &mut *((**rover).children).as_mut_ptr().offset(side as isize) })
            as *mut *mut RBTreeNode;
    }
    (unsafe { *rover = node });
    (unsafe { (*node).parent = parent });
    rb_tree_insert_case1(tree, node);
    (unsafe { (*tree).num_nodes += 1 });
    (unsafe { (*tree).num_nodes });
    return node;
}
#[no_mangle]
pub extern "C" fn rb_tree_lookup_node(
    mut tree: *mut RBTree,
    mut key: RBTreeKey,
) -> *mut RBTreeNode {
    let mut node: *mut RBTreeNode = 0 as *mut RBTreeNode;
    let mut side: RBTreeNodeSide = RB_TREE_NODE_LEFT;
    let mut diff: i32 = 0;
    node = unsafe { (*tree).root_node };
    while !node.is_null() {
        diff =
            unsafe { ((*tree).compare_func).expect("non-null function pointer")(key, (*node).key) };
        if diff == 0 as i32 {
            return node;
        } else if diff < 0 as i32 {
            side = RB_TREE_NODE_LEFT;
        } else {
            side = RB_TREE_NODE_RIGHT;
        }
        node = unsafe { (*node).children[side as usize] };
    }
    return 0 as *mut RBTreeNode;
}
#[no_mangle]
pub extern "C" fn rb_tree_lookup(mut tree: *mut RBTree, mut key: RBTreeKey) -> RBTreeValue {
    let mut node: *mut RBTreeNode = 0 as *mut RBTreeNode;
    node = rb_tree_lookup_node(tree, key);
    if node.is_null() {
        return 0 as *mut libc::c_void;
    } else {
        return unsafe { (*node).value };
    };
}
#[no_mangle]
pub extern "C" fn rb_tree_remove_node(mut _tree: *mut RBTree, mut _node: *mut RBTreeNode) {}
#[no_mangle]
pub extern "C" fn rb_tree_remove(mut tree: *mut RBTree, mut key: RBTreeKey) -> i32 {
    let mut node: *mut RBTreeNode = 0 as *mut RBTreeNode;
    node = rb_tree_lookup_node(tree, key);
    if node.is_null() {
        return 0 as i32;
    }
    rb_tree_remove_node(tree, node);
    return 1 as i32;
}
#[no_mangle]
pub extern "C" fn rb_tree_root_node(mut tree: *mut RBTree) -> *mut RBTreeNode {
    return unsafe { (*tree).root_node };
}
#[no_mangle]
pub extern "C" fn rb_tree_node_key(mut node: *mut RBTreeNode) -> RBTreeKey {
    return unsafe { (*node).key };
}
#[no_mangle]
pub extern "C" fn rb_tree_node_value(mut node: *mut RBTreeNode) -> RBTreeValue {
    return unsafe { (*node).value };
}
#[no_mangle]
pub extern "C" fn rb_tree_node_child(
    mut node: *mut RBTreeNode,
    mut side: RBTreeNodeSide,
) -> *mut RBTreeNode {
    if side as u32 == RB_TREE_NODE_LEFT as i32 as u32
        || side as u32 == RB_TREE_NODE_RIGHT as i32 as u32
    {
        return unsafe { (*node).children[side as usize] };
    } else {
        return 0 as *mut RBTreeNode;
    };
}
#[no_mangle]
pub extern "C" fn rb_tree_node_parent(mut node: *mut RBTreeNode) -> *mut RBTreeNode {
    return unsafe { (*node).parent };
}
#[no_mangle]
pub extern "C" fn rb_tree_to_array(mut _tree: *mut RBTree) -> *mut RBTreeValue {
    return 0 as *mut RBTreeValue;
}
#[no_mangle]
pub extern "C" fn rb_tree_num_entries(mut tree: *mut RBTree) -> i32 {
    return unsafe { (*tree).num_nodes };
}
